﻿#include "stdafx.h"
#include "MergeSort.h"

void MergeSort::Merge_Sort()
{
	int p,pb,pc; //các chỉ số trên các mảng a,b,c
	int i,k = 1; //độ dài của dãy con khi phân hoạch
	do {
		//tách a thành b và c
		p = pb = pc = 0;
		while(p<8){
			for(i = 0;(p<8)&&(i<k); i++)
				b[pb++] = a[p++];
			for(i = 0;(p<8)&&(i<k); i++)
				c[pc++] = a[p++];
		}
		Merge(pb,pc,k); //trộn b,c lại thành a
		k *= 2;
	}while(k<8);
}

void MergeSort::Merge(int nb, int nc, int k)
{
	int p,pb,pc,ib,ic,kb,kc;
	p = pb = pc = ib = ic = 0;
	while((0<nb)&&(0<nc)){
		kb = min(k,nb);
		kc = min(k,nc);
		if(b[pb+ib] <= c[pc+ic]){
			a[p++] = b[pb+ib]; 
			ib++;
			if(ib == kb){
				for(;ic<kc;ic++)
					a[p++] = c[pc+ic];
				pb += kb;
				pc += kc;
				ib = ic = 0;
				nb -= kb; 
				nc -= kc;
			}
		}
		else {
			a[p++] = c[pc+ic];
			ic++;
			if(ic == kc){
				for (;ib<kb; ib++)
					a[p++] = b[pb+ib];
				pb += kb;
				pc += kc;
				ib = ic = 0;
				nb -= kb ;
				nc -= kc;
			}
		}
	}
}